from typing import *


class Solution:
    '''
        超时
    '''

    def dicesProbability(self, n: int) -> List[float]:

        cnts = DefaultDict(int)

        def f(id, sum):
            if id == n:
                cnts[sum] += 1
                return
            for i in range(1, 7):
                f(id + 1, sum + i)

        f(0, 0)
        s = sum([v for k, v in cnts.items()])
        keys = sorted(cnts)
        return [cnts[key] / s for key in keys]


s = Solution()
print(s.dicesProbability(2))


class Solution:

    def dicesProbability(self, n: int) -> List[float]:
        mx = 6 * n + 1
        d = [0] * mx
        d[0] = 1
        for i in range(n):
            p = [0] * mx
            for j in range(1, 7):
                for k in range(mx - j):
                    p[j + k] += d[k]
            d = p
        s = sum(d)
        ans = []
        for i in range(1, mx):
            if d[i] != 0:
                ans.append(d[i] / s)
        return ans


s = Solution()
print(s.dicesProbability(2))